Dynamic recognition of synchronization operations for improved data race detection

ABSTRACT

Debugging multithreaded programs, which involves detection and identification of the cause of data races, has proved to be a hard problem. Although there has been significant amount of research on this topic, prior works rely on one important assumption - the debuggers must be aware of all the synchronization operations that take place during a program run. This assumption is a significant limitation as multithreaded programs, including the popular SPLASH-2 benchmark, have barriers and flag synchronizations implemented in the user code. We show that the lack of knowledge of these synchronization operations leads to unnecessary reporting of numerous races. Our experiments with SPLASH-2 benchmark suite show that 12-131 distinct segments in source code, on an average, give rise to well over 4 million dynamic instances of falsely reported races for these programs. We propose a dynamic software technique that identifies the user defined synchronizations exercised during a program run. This information not only helps avoids reporting of unnecessary races, but also helps a record/replay system to speedup the replay.

Our evaluation confirms that our synchronization detector is highly accurate with no false negatives and very few false positives. Thus, reporting of nearly all unnecessary races is avoided. Finally, we show that the knowledge of synchronization operations resulted in about 23% reduction in replay time.

References

1. S.V. Adve, M.D. Hill, B.P. Miller, and R.H.B. Netzer. Detecting data races on weak memory systems. In Proceedings of the 18th International Symposium on Computer Architecture (ISCA), volume 19, pages 234--243, New York, NY, 1991.
2. E. Artiaga, N. Navarro, X. Martorell, Y. Becerra, M. Gil, and A. Serra. Experiences on the implementation of parmacs macros using different multiprocessor operating system interfaces.
3. D.F. Bacon and S.C. Goldstein. Hardware-assisted replay of multiprocessor programs. In PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, pages 194--206, New York, NY, USA, 1991. ACM Press.
4. S. Bhansali, W.-K. Chen, S. de Jong, A. Edwards, R. Murray, M. Drinić, D. Mihocka, and J. Chau. Framework for instruction-level tracing and analysis of program executions. In VEE '06: Proceedings of the 2nd international conference on Virtual execution environments, pages 154--163, New York, NY, USA, 2006. ACM.
5. C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: preventing data races and deadlocks. In OOPSLA '02: Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pages 211--230, New York, NY, USA, 2002.
6. J.-D. Choi, B.P. Miller, and R.H.B. Netzer. Techniques for debugging parallel programs with flowback analysis. ACM Trans. Program. Lang. Syst., 13(4):491--530, 1991.
7. M. Christiaens and K. D. Bosschere. Trade, a topological approach to on-the-fly race detection in java programs. In JVM'01: Proceedings of the Java™ Virtual Machine Research and Technology Symposium on Java™ Virtual Machine Research and Technology Symposium, pages 15--15, Berkeley, CA, USA, 2001. USENIX Association.
8. A. Dinning and E. Schonberg. Detecting access anomalies in programs with critical sections. In PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, pages 85--96, New York, NY, USA, 1991. ACM Press.
9. C. Flanagan and S. N. Freund. Type-based race detection for Java. ACM SIGPLAN Notices, 35(5):219--232, 2000.
10. C. Flanagan and S. N. Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. SIGPLAN Not., 39(1):256--267, 2004.
11. R. Gupta. The fuzzy barrier: a mechanism for high speed synchronization of processors. In ASPLOS-III: Proceedings of the third international conference on Architectural support for programming languages and operating systems, pages 54--63, New York, NY, USA, 1989. ACM Press.
12. B. Krena, Z. Letko, R. Tzoref, S. Ur, and T. Vojnar. Healing data races on-the-fly. In PADTAD '07: Proceedings of the 2007 ACM workshop on Parallel and distributed systems: testing and debugging, pages 54--64, New York, NY, USA, 2007. ACM Press.
13. L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, 1978.
14. C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. SIGPLAN Not., 40(6):190--200, 2005.
15. P. Magnusson, A. Landin, and E. Hagersten. Queue locks on cache coherent multiprocessors. pages 165--171.
16. J. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on Supercomputing, pages 24--33, New York, NY, USA, 1991. ACM.
17. J.M. Mellor-Crummey and M.L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst., 9(1):21--65, 1991.
18. S. Narayanasamy, C. Pereira, and B. Calder. Recording shared memory dependencies using strata. In ASPLOS-XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, pages 229--240, New York, NY, USA, 2006. ACM Press.
19. S. Narayanasamy, G. Pokam, and B. Calder. Bugnet: Continuously recording program execution for deterministic replay debugging. In ISCA '05: Proceedings of the 32nd annual international symposium on Computer Architecture, pages 284--295, Washington, DC, USA, 2005. IEEE Computer Society.
20. S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards, and B. Calder. Automatically classifying benign and harmful data racesallusing replay analysis. In PLDI '07: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, pages 22--31, New York, NY, 2007.
21. N. Nethercote and J. Seward. How to shadow every byte of memory used by a program. In VEE '07: Proceedings of the 3rd international conference on Virtual execution environments, pages 65--74, New York, NY, USA, 2007. ACM Press.
22. R. H. B. Netzer. Optimal tracing and replay for debugging shared-memory parallel programs. In PADD '93: Proceedings of the 1993 ACM/ONR workshop on Parallel and distributed debugging, pages 1--11, New York, NY, USA, 1993. ACM Press.
23. R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 167--178, New York, NY, USA, 2003. ACM Press.
24. V. Project. Helgrind, a data race detector. In http://valgrind.org/docs/manual/hg-manual.html, 2003.
25. M. Ronsse and K.D. Bosschere. Recplay: a fully integrated practical record/replay system. ACM Trans. Comput. Syst., 17(2):133--152, 1999.
26. Y. Saito. Jockey: a user-space library for record-replay debugging. In AADEBUG'05: Proceedings of the sixth international symposium on Automated analysis-driven debugging, pages 69--76, New York, NY, USA, 2005. ACM.
27. A. Sasturkar, R. Agarwal, L. Wang, and S. D. Stoller. Automated type-based analysis of data races and atomicity. In PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 83--94, New York, NY, USA, 2005. ACM Press.
28. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: a dynamic data race detector for multi-threaded programs. In SOSP '97: Proceedings of the sixteenth ACM symposium on Operating systems principles, pages 27--37, New York, NY, USA, 1997. ACM Press.
29. C. von Praun and T. R. Gross. Object race detection. In OOPSLA '01: Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, pages 70--82, New York, NY, USA, 2001. ACM.
30. S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The SPLASH-2 programs: Characterization and methodological considerations. In Proceedings of the 22th International Symposium on Computer Architecture, pages 24--36, Santa Margherita Ligure, Italy, 1995.
31. M. Xu, R. Bodik, and M. D. Hill. A flight data recorder for enabling full-system multiprocessor recorder for enabling full-system multiprocessor deterministic replay. In ISCA '03: Proceedings of the 30th annual international symposium on Computer architecture, pages 122--135, New York, NY, USA, 2003. ACM Press.
32. Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: efficient detection of data race conditions via adaptive tracking. In SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles, pages 221--234, New York, NY, USA, 2005. ACM Press.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging